// https://leetcode.cn/problems/partition-array-into-disjoint-intervals/
// Created by ade on 2022/10/24.
// 要求left中每个元素都要<= right中的每个元素
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 解错了，这种是left中每个对应位置小于等于right中每个
    /*int len = 0;

    int partitionDisjoint1(vector<int> &nums) {
        int left = 0, right = 1;
        len = nums.size();
        while (nums[0] > nums[right]) right++;
        int a = dfs(0, right, nums);
        return a;
    }

    int dfs(int left, int right, vector<int> &nums) {
        if (right == len) return right - 1;
        int end = right;
        cout << "left:" << left << ",right:" << right << endl;
        while (left < end && right < len) {
            if (nums[left] < nums[right]) {
                left++;
                right++;
            } else {
                return dfs(0, right + 1, nums);
            }
        }
        cout << "end:" << end << endl;
        return end;
    }*/

    int partitionDisjoint(vector<int> &nums) {
        int len = nums.size();
        vector<int> minArr(len);
        vector<int> maxArr(len);
        minArr[len - 1] = nums[len - 1];
        maxArr[0] = nums[0];
        for (int i = 1; i < len; i++) {
            maxArr[i] = max(maxArr[i - 1], nums[i]);
            minArr[len - 1 - i] = min(minArr[len - i], nums[len - 1 - i]);
        }
        for (int i = 0; i < len - 1; i++) {
            if (maxArr[i] <= minArr[i + 1]) return i + 1;
        }
        return len - 1;
    }
};

int main() {
    Solution so;
    vector<int> nums = {5, 0, 3, 8, 6};
    cout << so.partitionDisjoint(nums);

    return 0;
}